西瓜书看了有一阵子了，终于看到了SVM，遥想研一看SVM的时候。。我操 这是什么。。这又是什么。。论高中数学的重要性的，出来混都是要还的。只好一点一点补齐SVM中用到的各种知识点。今天先扯一扯自己对拉格朗日乘子法和KKT条件的理解，希望这篇文章写完之后，能让我对这2个臭逼玩意能有更好的理解，那么现在开始。
我们为什么在SVM中要用到拉格朗日和KKT条件！！！
因为在SVM中我们要计算一个有约束条件的极值问题，而拉格朗日乘子法和KKT条件是非常重要的两个求取方法。
对于等式约束的优化问题（就是限制的那个式子是个等式 s.t h(x) = 0 类似这种），可以应用拉格朗日乘子法去求取最优值。
如果含有不等式约束，可以应用KKT条件去求取最优值。
这两种方法求得的结果只是必要条件，只有当是凸函数（二次导数大于0为凸）的情况下，才能保证是充分必要条件。而KKT条件是拉格朗日乘子法的泛化。
下面我就针对这两个玩意，谈一谈我的理解。
拉格朗日乘子法！！！
拉格朗日乘子法在考研的数学二中就用到过，当时只知道要那么用，那么用就能解决条件极值的问题，但是真心不知道为什么，这次先把为什么可以用拉格朗日说一下。
想象一下，目标函数f(x,y)是一座山的高度，约束g(x,y)=C是镶嵌在山上的一条曲线如下图。（渣画技看看就好了）
你为了找到曲线上的最低点，就从最低的等高线（0那条）开始网上数。数到第三条，等高线终于和曲线有交点了（如上图所示）。因为比这条等高线低的地方都不在约束范围内，所以这肯定是这条约束曲线的最低点了。
而且约束曲线在这里不可能和等高线相交，一定是相切。因为如果是相交的话，如下图所示，那么曲线一定会有一部分在B区域，但是B区域比等高线低，这是不可能的。假设g(x)与等高线相交，交点就是同时满足等式约束条件和目标函数的可行域的值，但肯定不是最优值，因为相交意味着肯定还存在其它的等高线在该条等高线的内部或者外部，使得新的等高线与目标函数的交点的值更大或者更小，只有到等高线与目标函数的曲线相切的时候，可能取得最优值。
两条曲线相切，意味着他们在这点的法线平行，也就是法向量只差一个任意的常数乘子（取为-λ）：
∇f（x, y) = -λ(∇g(x,y)-C) 把这个式子的右边移动到左边，就得到∇（f(x,y)+λ(g(x,y)-C)=0
在看看这个式子，你又能想起来什么呢？高中数学。。。这个就是f(x,y)+λ(g(x,y)-C)没有约束情况下极值点的充分条件吧。。（令其导数等于0，求极值点。。。高中用的就是这个套路。。哎）所以证明了拉格朗日乘子法确实可以解决这类问题，拉格朗日确实牛逼。。高中数学也应该好好学 哎。难受啊。
那拉格朗日乘子法到底是怎么用的呢？简单的再说一下就是 把等式约束hi(x)用一个系数与f(x)写为一个式子，称为拉格朗日函数，而系数称为拉格朗日乘子。通过拉格朗日函数对各个变量求导，令其为零，可以求得候选值集合，然后验证求得最优值。
KKT条件！！！！！
我先给出KKT条件：
对于具有等式和不等式约束的一般优化问题：
KKT条件给出了判断X*是否是最优解的必要条件：
不等式约束优化问题
我们先给出其主要思想：转化的思想——将不等式约束条件变成等式约束条件.具体做法：引入松弛变量.松弛变量也是优化变量，也需要一视同仁求偏导.
具体来说，我们先看一个一元函数的例子：
min f(x)
s.t. g1(x) = a - x ≤ 0
g2(x) = x - b ≤ 0
（注：优化问题中，我们必须求得一个确定的值，因此不妨令所有的不等式均取到等号，即≤的情况.）
对于约束g1和g2,我们分别引入两个松弛变量a₁²和b₁²,得到h1(x,a₁) = g1 + a₁² = 0和h2(x,b₁) = g2 + b₁² = 0,这里直接加上平方项a₁²和b₁²而非a₁和b₁,是因为g1和g2这两个不等式的左边必须加上一个正数（或者0）才能使不等式变成等式。若只加上a₁和b₁,又会引入新的约束a₁≥0,b₁≥0.这岂不是很爆炸！！！
由此我们将不等式约束转化为了等式约束，并得到了拉格朗日函数
L（x,a₁,b₁,u₁,u₂) = f(x) + u₁(a - x + a₁²) + u₂(x - b + b₁²)
我们再按照等式约束优化问题对齐求解，联立方程组：
（注：这里的u₁ ≥ 0,u₂ ≥ 0先承认，等会再解释，实际上对于不等式约束前的乘子，我们要求其大于等于0）
得出方程组后，便开始手动解，先看第3行的两个式子 u₁a₁ = 0 和 u₂b₁ = 0比较简单，我们就从他们入手。
对于u₁a₁ = 0,我们有两种情况:
情形1: u₁ = 0,a₁ ≠ 0:
此时由于乘子u₁ = 0,因此g1与其相乘为0，可以理解为约束g1不起作用，且有g1(x) = a - x < 0 (因为a₁ ≠ 0 , 所以他的平方一定是大于0的）
情形2：u₁ ≥ 0 , a₁ = 0
此时，g1(x) = a - x = 0 且 u1 > 0 (因为a₁ = 0 为了 a - x + a₁² = 0 ， 所以 a - x必须等于0），可以理解为约束g1起作用了，且有g1(x) = 0
合并两种情况的：u1g1 = 0 且在约束起作用时,u₁ > 0,g1(x) = 0;约束不起作用时u1 = 0,g1(x) < 0
同样的，分析u₂b₁ = 0,可得出约束g2起作用和不起作用的情形，并分析得到u₂g₂ = 0
由此，方程组（极值必要条件）转化为：
这是一元一次的情形，类似的，对于多远多次不等式约束问题
min f(x)
s.t.g_j(x) ≤ 0 ( j = 1,2,````,m)
我们有
上式便称为不等式约束优化问题的KKT（Karush-Kuhn-Tucker）条件u_j称为KKT乘子，且约束起作用时u_j＞0,g_j(x) = 0;约束不起作用时u_j = 0,g_j(x) < 0.
总结：同时包含等式和不等式约束的一般优化问题
注意，对于等式约束的Lagrange乘子，并没有非负的要求！以后求其极值点，不必再引入松弛变量，直接使用KKT条件判断！
